#include "rb_tree.c"

rb_node_t *rb_first(rb_root_t *root)
{
	rb_node_t *n;
	n = root->node;
	if (!n)
		return NULL;
	while(n->left)
		n = n->left;
	return n;
}

rb_node_t *rb_last(rb_root_t *root)
{
	rb_node_t *n;
	n = root->node;
	if (!n)
		return NULL;
	while(n->right)
		n = n->right;
	return n;
}

rb_node_t *rb_next(rb_node_t *node)
{
	rb_node_t *parent;

	if (node->right) {
		node = node->right;
		while(node->left)
			node = node->left;
		return node;
	}
	
	do {
		parent = node->parent;
		if(node == parent->left)
			break;
		node = parent;
	} while(parent);

	return parent;

}

rb_node_t *rb_prev(rb_node_t *node)
{
	rb_node_t *parent;

	if (node->left) {
		node = node->left;
		while(node->right)
			node = node->right;
		return node;
	}

	do {
		parent = node->parent;
		if (node == parent->right)
			break;
	} while(parent);

	return parent;
}
